{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T05:00:51Z","timestamp":1755925251559},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1993,3]]},"abstract":"<jats:p> Multidimensional digital searching (M-d tries) is analyzed from the view point of partial match retrieval. Our first result extends the analysis of Flajolet and Puech of the average cost of retrieval under the Bernoulli model to biased probabilities of symbols occurrences in a key. The second main finding concerns the variance of the cost of the retrieval in the unbiased case. This variance is of order O(N<jats:sup>1\u2212s\/M<\/jats:sup>) where N is the number of records stored in an M-d trie, and s is the number of specified components in a query of size M. For M=2 and s=1 we present a detailed analysis of the variance, which identifies the constant at [Formula: see text]. This analysis, which is the central part of our paper, requires certain series transformation identities which go back to Ramanujan. In the Appendix we provide a Mellin transform approach to these results. <\/jats:p>","DOI":"10.1142\/s0129054193000055","type":"journal-article","created":{"date-parts":[[2004,11,22]],"date-time":"2004-11-22T22:29:30Z","timestamp":1101162570000},"page":"69-84","source":"Crossref","is-referenced-by-count":11,"title":["MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS IN TRIES"],"prefix":"10.1142","volume":"04","author":[{"given":"PETER","family":"KIRSCHENHOFER","sequence":"first","affiliation":[{"name":"Department of Algebra and Discrete Mathematics, Technical University of Vienna, Vienna A-1040, Austria"}]},{"given":"HELMUT","family":"PRODINGER","sequence":"additional","affiliation":[{"name":"Department of Algebra and Discrete Mathematics, Technical University of Vienna, Vienna A-1040, Austria"}]},{"given":"WOJCIECH","family":"SZPANKOWSKI","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Purdue University,  West Lafayette, IN 47907, U.S.A."}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054193000055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:55:32Z","timestamp":1565124932000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054193000055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,3]]}},"alternative-id":["10.1142\/S0129054193000055"],"URL":"https:\/\/doi.org\/10.1142\/s0129054193000055","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}