Abstract
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 keys, since each search requires Θ(log 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 “suitable” disorder gives better bounds than those derivable by using the natural lexicographic order.
We start from previous work done by Andersson et al. [2001], who proved that Θ(k log log n/log log(4 + klog log n/log n) + k + log n) character comparisons (or probes) comprise the tight complexity for searching a plain sorted array of n keys, each of length k, arranged in lexicographic order. We describe a novel permutation of the n keys that is different from the sorted order. When keys are kept “unsorted” in the array according to this permutation, the complexity of searching drops to Θ(k + log n) character comparisons (or probes) in the worst case, which is optimal 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 Θ(log n) when k = O(1). More implications are discussed in the article, including searching in the bit-probe model.
- Andersson, A., Hagerup, T., Håstad, J., and Petersson, O. 2001. Tight bounds for searching a sorted array of strings. SIAM J. Comput. 30, 5 (Oct.), 1552--1578. Google ScholarDigital Library
- Andersson, A., Håstad, J., and Petersson, O. 1995. A tight lower bound for searching a sorted array. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (STOC). ACM Press. Google ScholarDigital Library
- Andersson, A., Hagerup, T., Håstad, J., and Petersson, O. 1994. The complexity of searching a sorted array of strings. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (STOC), Montreal, Quebec, Canada. ACM Press, 317--325. Google ScholarDigital Library
- Bentley, J. L., and Sedgewick, R. 1997. Fast algorithms for sorting and searching strings. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA. ACM Press, 360--369. Google ScholarDigital Library
- Elias, P., and Flower, R. A. 1975. The complexity of some simple retrieval problems. J. ACM 22, 3, 367--379. Google ScholarDigital Library
- Fiat, A., and Naor, M. 1993. Implicit O(1) probe search. SIAM J. Comput. 22, 1, 1--10. Google ScholarDigital Library
- Fiat, A., and Naor, M. 1989. Implicit O(1) probe search. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), Seattle, WA. ACM Press, 336--344. Google ScholarDigital Library
- Fiat, A., Naor, M., Schmidt, J. P., and Siegel, A. 1992. Nonoblivious hashing. J. ACM 39, 4 (Oct.), 764--782. Google ScholarDigital Library
- Fiat, A., Munro, J. I., Naor, M., Schäffer, A. A., Schmidt, J. P., and Siegel, A. 1991. An implicit data structure for searching a multikey table in logarithmic time. J. Comput. Syst. Sci. 43, 3 (Dec.), 406--424.Google ScholarCross Ref
- Fiat, A., Naor, M., Schmidt, J., and Siegel, A. 1988. Non-Oblivious hashing. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), Chicago. IL. ACM Press, 367--376. Google ScholarDigital Library
- Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a sparse table with O(1) worst case access time. J. ACM 31, 3, 538--544. Google ScholarDigital Library
- Hirschberg, D. S. 1980. On the complexity of searching a set of vectors. SIAM J. Comput. 9, 1, 126--129.Google ScholarCross Ref
- Hirschberg, D. S. 1978. A lower worst-case complexity for searching a dictionary. In Proceedings of the 16th Annual Allerton Conference on Communication, Control, and Computing, 50--53.Google Scholar
- Knuth, D. E. 1998. The Art of Computer Programming III: Sorting and Searching (2nd ed.). Addison-Wesley, Reading, MA. Google ScholarDigital Library
- Kosaraju, S. R. 1979. On a multidimensional search problem. In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC), 67--73. Google ScholarDigital Library
- Manber, U., and Myers, G. 1993. Suffix arrays: A new method for on-line string searches. SIAM J. Comput. 22, 5 (Oct.), 935--948. Google ScholarDigital Library
- Munro, J. I. 1986. An implicit data structure supporting insertion, deletion, and search in O(log2 n) time. J. Comput. Syst. Sci. 33, 1, 66--74. Google ScholarDigital Library
- Munro, J. I., and Suwanda, H. 1980. Implicit data structures for fast search and update. J. Comput. Syst. Sci. 21, 2, 236--250.Google ScholarCross Ref
- Yao, A. C. 1984. Should tables be sorted? J. ACM 31, 245--281.Google ScholarDigital Library
Index Terms
- No sorting? better searching!
Recommendations
Faster deterministic sorting and searching in linear space
FOCS '96: Proceedings of the 37th Annual Symposium on Foundations of Computer ScienceWe present a significant improvement on linear space deterministic sorting and searching. On a unit-cost RAM with word size w, an ordered set of n w-bit keys (viewed as binary strings or integers) can be maintained in O(min{[/spl radic/(logn)][logn/logw+...
Searching, Merging, and Sorting in Parallel Computation
We study the number of comparison steps required for searching, merging, and sorting with P processors. We present a merging algorithm that is optimal up to a constant factor when merging two lists of equal size (independent of the number of processors);...
No Sorting? Better Searching!
FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer ScienceSorting is commonly meant as the task of arranging keys in increasing or decreasing order (or small variations of this order). Given n keys underlying a total order, the best organization in an array is maintaining them in sorted order. Searching ...
Comments