NDLI: No sorting? Better searching! [optimal array organization]

Content Provider	IEEE Xplore Digital Library
Author	Franceschini, G. Grossi, R.
Copyright Year	2004
Description	Author affiliation: Dipt. di Informatica, Universita di Pisa, Italy (Franceschini, G.)
Abstract	Sorting 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 requires /spl Theta/ (log n) comparisons in the worst case, which is optimal. We demonstrate that this basic fact in data structures does not hold for the general case of multidimensional keys, whose comparison cost is proportional to their length. In two papers by Andersson et al. (1994) and Andersson et al. (1995) and the full version in 2001, Andersson et al. study the complexity of searching a sorted array of n keys, each of length k, arranged in lexicographic (or alphabetic) order for an arbitrary, possibly unbounded, ordered alphabet. They give sophisticated arguments for proving a tight bound in the worst case for this basic data organization, up to a constant factor, obtaining /spl Theta/(((k log log n)/(log log (4 + ((k log log n)/log n)))) + k log n) character comparisons (or probes). Note that the bound is /spl Theta/ (log n) when k = 1, which is the case that is well known in algorithmics. We describe a permutation of the n keys that is different from the sorted order, and sorting is just the starting point for describing our preprocessing. When keys are stored according to this "unsorted" order in the array, the complexity of searching drops to /spl Theta/ (k + log n) character comparisons (or probes) in the worst case, which is optimal among all possible permutations of the n keys in the array, up to a constant factor. Again, the bound is /spl Theta/ (log n) when k = 1. Jointly with the aforementioned result of Anders son et al., our finding provably shows that keeping k-dimensional keys sorted in an array is not the best data organization for searching. This fact was not observable before by just considering k = O(1) as sorting is an optimal organization in this case. More implications of our result are commented in the introduction.
Sponsorship	IEEE Comput. Soc. Tech. Soc. on Foundations of Comput
Starting Page	491
Ending Page	498
File Size	157441
Page Count	8
File Format	PDF
ISBN	0769522289
ISSN	02725428
DOI	10.1109/FOCS.2004.43
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-10-17
Publisher Place	Italy
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Sorting Probes Algorithm design and analysis Data structures Costs Dictionaries Books Time measurement Computer science
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in