{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:38:51Z","timestamp":1750307931825,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            Questions about order versus disorder in systems and models have been fascinating scientists over the years. In computer science, order is intimately related to sorting, commonly meant as the task of arranging keys in increasing or decreasing order with respect to an underlying total order relation. The sorted organization is amenable for searching a set of\n            <jats:italic>n<\/jats:italic>\n            keys, since each search requires \u0398(log\n            <jats:italic>n<\/jats:italic>\n            ) comparisons in the worst case, which is optimal if the cost of a single comparison can be considered a constant. Nevertheless, we prove that disorder implicitly provides more information than order does. For the general case of searching an array of multidimensional keys whose comparison cost is proportional to their length (and hence which cannot be considered a constant), we demonstrate that \u201csuitable\u201d disorder gives better bounds than those derivable by using the natural lexicographic order.\n          <\/jats:p>\n          <jats:p>\n            We start from previous work done by Andersson et al. [2001], who proved that \u0398(\n            <jats:italic>k<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            \/log log(4 +\n            <jats:italic>k<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            \/log\n            <jats:italic>n<\/jats:italic>\n            ) +\n            <jats:italic>k<\/jats:italic>\n            + log\n            <jats:italic>n<\/jats:italic>\n            ) character comparisons (or probes) comprise the tight complexity for searching a plain sorted array of\n            <jats:italic>n<\/jats:italic>\n            keys, each of length\n            <jats:italic>k<\/jats:italic>\n            , arranged in lexicographic order. We describe a novel\n            <jats:italic>permutation<\/jats:italic>\n            of the\n            <jats:italic>n<\/jats:italic>\n            keys that is different from the sorted order. When keys are kept \u201cunsorted\u201d in the array according to this permutation, the complexity of searching drops to \u0398(\n            <jats:italic>k<\/jats:italic>\n            + log\n            <jats:italic>n<\/jats:italic>\n            ) character comparisons (or probes) in the worst case, which is\n            <jats:italic>optimal<\/jats:italic>\n            among all possible permutations, up to a constant factor. Consequently, disorder carries more information than does order; this fact was not observable before, since the latter two bounds are \u0398(log\n            <jats:italic>n<\/jats:italic>\n            ) when\n            <jats:italic>k<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (1). More implications are discussed in the article, including searching in the bit-probe model.\n          <\/jats:p>","DOI":"10.1145\/1328911.1328913","type":"journal-article","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T16:08:32Z","timestamp":1207066112000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["No sorting? better searching!"],"prefix":"10.1145","volume":"4","author":[{"given":"Gianni","family":"Franceschini","sequence":"first","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[{"name":"University di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797329889"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225171"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195175"},{"volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bentley J. L.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321899"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73039"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146591"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90022-W"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62248"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209012"},{"volume-title":"Proceedings of the 16th Annual Allerton Conference on Communication, Control, and Computing, 50--53","year":"1978","author":"Hirschberg D. S.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"Knuth D. E. 1998. The Art of Computer Programming III: Sorting and Searching (2nd ed.). Addison-Wesley Reading MA.   Knuth D. E. 1998. The Art of Computer Programming III: Sorting and Searching (2nd ed.). Addison-Wesley Reading MA."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804399"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90043-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90037-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328913","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328911.1328913","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:00Z","timestamp":1750258320000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328913"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1328911.1328913"],"URL":"https:\/\/doi.org\/10.1145\/1328911.1328913","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}