{"entities":{"Q1662625":{"pageid":1673366,"ns":120,"title":"Item:Q1662625","lastrevid":68175279,"modified":"2026-04-12T21:56:12Z","type":"item","id":"Q1662625","labels":{"en":{"language":"en","value":"Towards efficient positional inverted index"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6920575"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$04BD831C-817F-4147-A458-A9CB7A3C544D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7026611c3eaa01aad64a9ce5bebc42797550e27f","datavalue":{"value":{"text":"Towards efficient positional inverted index","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1662625$0DB9DBF1-8DAC-4844-9112-A66DD5547D2B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9c03bffe52c956b03e4c80554108c9c6ec807c23","datavalue":{"value":"1461.68238","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662625$6E90E6BC-AACC-4107-8774-FAD435F83B87","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b2fe6733138712ab54ed3fcdded0397fefd5a1a","datavalue":{"value":{"entity-type":"item","numeric-id":954953,"id":"Q954953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$F27CC5E6-ED05-4C87-8C8F-8FAD06502750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5cf5ddc8793d78e3029b84473a3924a817877f85","datavalue":{"value":{"entity-type":"item","numeric-id":1434669,"id":"Q1434669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$BF6120A2-3250-48A7-8BC9-E1DAD044993B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$5F8755DA-F67A-402A-94E0-37D273CFC3C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"431a43c637c8a2264e4d8145aa5a3c26bfb96786","datavalue":{"value":{"time":"+2018-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1662625$3436EF96-3E79-418A-BD77-1A1EABA6ED0F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8b06cb2a76f2bca65d39e389c4d46e492ac82200","datavalue":{"value":"Summary: We address the problem of positional indexing in the natural language domain. The positional inverted index contains the information of the word positions. Thus, it is able to recover the original text file, which implies that it is not necessary to store the original file. Our \\textit{Positional Inverted Self-Index} (\\texttt{PISI}) stores the word position gaps encoded by variable byte code. Inverted lists of single terms are combined into one inverted list that represents the backbone of the text file since it stores the sequence of the indexed words of the original file. The inverted list is synchronized with a presentation layer that stores separators, \\textit{stop words}, as well as variants of the indexed words. The Huffman coding is used to encode the presentation layer. The space complexity of the inverted list is \\(\\mathcal{O}((N - n) \\lceil \\log_{2^b} N \\rceil +(\\lfloor \\frac{N - n}{\\alpha} \\rfloor + n) \\times(\\lceil \\log_{2^b} n \\rceil + 1))\\) where \\(N\\) is a number of stems, \\(n\\) is a number of unique stems, \\(\\alpha\\) is a step/period of the \\textit{back pointers} in the inverted list and \\(b\\) is the size of the word of computer memory given in bits. The space complexity of the presentation layer is \\(\\mathcal{O}(- \\sum_{i = 1}^N \\lceil \\log_2 p_i^{n(i)} \\rceil - \\sum_{j = 1}^{N'} \\lceil \\log_2 p_j' \\rceil + N)\\) with respect to \\(p_i^{n(i)}\\) as a probability of a stem variant at position \\(i\\), \\(p_j^\\prime\\) as the probability of separator or stop word at position \\(j\\) and \\(N^\\prime\\) as the number of separators and stop words.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662625$41DF31E7-00A2-416F-8AB5-C69DBEEE8808","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ae62b6ae8284bad4753b7ed23b6f2503aa5e4b9f","datavalue":{"value":"68T50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662625$185C0635-BBA8-4813-90C6-ECFDDE6C589F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662625$B568E598-713B-4183-A1B9-7FDF41974580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662625$373D4545-67BB-485B-B589-13BA239C1333","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a131e2675b6121f64bcbb2b2cf9dffabe4ea7b87","datavalue":{"value":"6920575","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662625$15A8E6D6-DADE-4F98-B77D-EFBA0B2D16F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d446666e83f53b1db6e3f354dbaae95cea5694fd","datavalue":{"value":"inverted index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662625$E885D9B2-1BD7-49B6-8844-50A1C300273F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5805cdcbf205bd2c84f60374303c22aab2f2950a","datavalue":{"value":"search engines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662625$8CC77205-B192-473F-A081-A8A987BD1648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47decf00b165ee8ea3ad144834632fcd9332ddf7","datavalue":{"value":"self-indexing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662625$7E437C47-586D-49B5-ADFA-0A0ED5BA9ED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d0bd6d92a74377228213483b7f0e15b2d9fd3fb","datavalue":{"value":"natural language processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662625$34E6D0E5-ACB3-40BB-A379-9CAC730FAF7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99de46d71759c0d7b682d826cd549f3d1ed09133","datavalue":{"value":"data compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662625$E22449C1-C64B-44AA-A867-9E73EB1D2507","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$C52F6A7F-54F3-4DA1-B287-79CA7D01777E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6cf6700358507a0480db66ca7747efd29352fb4a","datavalue":{"value":"https://doi.org/10.3390/a10010030","type":"string"},"datatype":"url"},"type":"statement","id":"Q1662625$661AF6F1-6242-4F91-BE5D-14B04DA8EE60","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f11e1f60950811aaa75b16f12aa74c160fab3121","datavalue":{"value":"W2591309672","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662625$649ADDB5-F06D-4E74-954E-5F45F6D1A5E3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0bcfd521f72c778ad93ac802ec5f5605c162f5a","datavalue":{"value":{"entity-type":"item","numeric-id":5515793,"id":"Q5515793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$9E601F87-8420-4756-800C-436FE4A839FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44e85ba57e9ab8eefde4f3b7c1b1ce77ed79d631","datavalue":{"value":{"entity-type":"item","numeric-id":4053461,"id":"Q4053461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$0308F1FD-160D-4B3C-AC30-9317957A3950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c832995d7ed504d8d881ac4c85c6a7ea6e61e4c","datavalue":{"value":{"entity-type":"item","numeric-id":3011842,"id":"Q3011842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$6C95F5A0-F5DA-4298-8C79-7E296309FFC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9c0f6c12d8ae5a3a9d115b1a1d9acbb6131623f","datavalue":{"value":{"entity-type":"item","numeric-id":2944557,"id":"Q2944557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$67E2F637-0F01-4727-B011-B9D7CC1A7371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"727111afb31ec0e742cb8fa2bbbff66ccf52225a","datavalue":{"value":{"entity-type":"item","numeric-id":5897136,"id":"Q5897136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$5DA1DB0C-5734-4CBC-B069-B9F7FE73CB69","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0524ffa4c8f3bd5d198835ee700dec428b5b4a6b","datavalue":{"value":"10.3390/A10010030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662625$986A7BC0-A3DE-4141-8FF8-4B3B1B26BB7A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2abfbee2767a3fc27ee98826dbb0a87fe930a582","datavalue":{"value":{"entity-type":"item","numeric-id":4458870,"id":"Q4458870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d405d205a6ea6cb2c523081507c21c2dc6dcf4de","datavalue":{"value":{"amount":"+0.7362988591194153","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662625$6EBC3020-B353-44B5-9F00-EF13AA9721FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cf5de0c47d48cf9d5c49f22893324cf0615dd7a","datavalue":{"value":{"entity-type":"item","numeric-id":5222002,"id":"Q5222002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8a70be6ee5d8b57822da55bea081e433beeb215","datavalue":{"value":{"amount":"+0.7353544235229492","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662625$9AB10B9B-18AF-48EA-8DD4-05AACF0FE0FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fee61f35a0e60cb41d8bebcc9b31e233456a4d0a","datavalue":{"value":{"entity-type":"item","numeric-id":5232571,"id":"Q5232571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9ee425c7c07dd7b525c7df730bd240d1274a512","datavalue":{"value":{"amount":"+0.7343236804008484","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662625$74DE0BF4-A1A4-4D8F-AA26-F40E4DE203D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5b96bc433441e71c549b23fe3c5ab7737e96839","datavalue":{"value":{"entity-type":"item","numeric-id":2768307,"id":"Q2768307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a4f03fa3c00ea959784f66fafcb24bf159d4983","datavalue":{"value":{"amount":"+0.7266442775726318","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662625$A72D68B7-025F-4CA8-84E6-E03FE607408E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64d6dff56c1b5c1c336256a30d603182cebbb697","datavalue":{"value":{"entity-type":"item","numeric-id":5897945,"id":"Q5897945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a4f03fa3c00ea959784f66fafcb24bf159d4983","datavalue":{"value":{"amount":"+0.7266442775726318","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662625$D66DD52D-AB37-4847-AD2B-D851B3E30C31","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662625$0D803518-C315-4BBF-B1E3-E244CAE874A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Towards efficient positional inverted index","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Towards_efficient_positional_inverted_index"}}}}}