Multi-faceted search
A facility for representing a set of items each potentially having a value for each of a group of attributes is described. The items are represented in a database made up of two or more discrete components. Each component corresponds to a proper subset of group of attributes, and represents for every item of the set the values of its proper subset of attributes. Every component is organized such that data items are represented within it in the same order.
1. A method in a computing system for identifying from an initial sequence in arbitrary order of items each having a sort value those items that should be included on the mth page of n items of a fully-sorted sequence of the items, comprising:
(a) initializing a working sequence having the same order as the initial sequence;
(b) after (a), for each of pages 1 to m:
determining whether any item in the first n positions of the working sequence has a sort value smaller than the sort value of any position of the working sequence greater than n,
if it is determined that an item in the first n positions of the working sequence has a sort value smaller than the sort value of any position of the working sequence greater than n, until none of the items in the first n positions of the working sequence has a sort value smaller than the sort value of any position of the working sequence greater than n,
subjecting the working sequence to a repeatable exchange sort;
once none of the items in the first n positions of the working sequence has a sort value smaller than the sort value of any position of the working sequence greater than n, if the current page is less than m, removing the first n positions from the working sequence; and
(c) after (b), identifying the items in the first n positions of the working sequence.
2. The method of claim 1 , further comprising:
sorting the identified items until they are ordered in accordance with their sort value; and
displaying the sorted identified items.
3. The method of claim 2 wherein the identified items are sorted using an insertion sort.
4. The method of claim 1 wherein the repeatable exchange sort to which the working sequence is subjected is a quicksort.
5. The method of claim 1 wherein the repeatable exchange sort to which the working sequence is subjected is a truncated quicksort.
6. The method of claim 1 wherein the repeatable exchange sort to which the working sequence is subjected is a quicksort using a fat pivot.
7. The method of claim 1 wherein the repeatable exchange sort to which the working sequence is subjected is a quicksort that deterministically selects pivot locations.
8. The method of claim 1 wherein the repeatable exchange sort to which the working sequence is subjected is a quicksort that selects a central position in the working sequence as the pivot location.
9. The method of claim 1 , further comprising:
receiving a query;
receiving a page size;
receiving a page number to return;
receiving a sort attribute; and
receiving a sort direction.
10. A computing system, having a memory and a processor, configured to identify from an initial sequence in arbitrary order of items each having a sort value those items that should be included on the mth page of n items of a fully-sorted sequence of the items, the computing system comprising:
an initialization component configured to initialize a working sequence having the same order as the initial sequence and to initialize a sorting window to empty; and
a sorting component configured to, after the working sequence and the sorting window are initialized, for each page of pages 1 to m:
subject the working sequence, exclusive of the sorting window, to a repeatable exchange sort only until none of the items in the first n positions of the working sequence, exclusive of the sorting window, has a sort value smaller than the sort value of any position of the working sequence, exclusive of the sorting window, greater than n; and
expand the sorting window to include the positions in the current page; wherein the initialization component and the sorting component each comprise computer-executable instructions stored in the memory for execution by the processor.
11. A computer-readable storage device storing content that, when executed by a computing system having a processor, causes the computing system to perform a method for identifying, from an initial sequence in arbitrary order of items each having a sort value, those items that should be included on the mth page of n items of a fully-sorted sequence of the items, the method comprising:
(a) initializing a working sequence having the same order as the initial sequence;
(b) after (a), for each of pages 1 to m:
subjecting the working sequence to a repeatable exchange sort only until none of the items in the first n positions of the working sequence has a sort value larger than the sort value of any position of the working sequence greater than n;
once none of the items in the first n positions of the working sequence has a sort value larger than the sort value of any position of the working sequence greater than n, if the current page is less than m, removing the first n positions from the working sequence; and
(c) after (b), identifying the items in the first n positions of the working sequence.
12. The computer-readable storage device of claim 11 , the method further comprising:
sorting the identified items until they are ordered in accordance with their sort value; and
displaying the sorted identified items.
13. The computer-readable storage device of claim 11 wherein the identified items are sorted using an insertion sort.
14. The computer-readable storage device of claim 11 wherein the repeatable exchange sort to which the working sequence is subjected is a quicksort.
15. The computer-readable storage device of claim 11 wherein the repeatable exchange sort to which the working sequence is subjected is a truncated quicksort.
16. The computer-readable storage device of claim 11 wherein the repeatable exchange sort to which the working sequence is subjected is a quicksort using a fat pivot.
17. The computer-readable storage device of claim 11 wherein the repeatable exchange sort to which the working sequence is subjected is a quicksort that deterministically selects pivot locations.
18. The computer-readable storage device of claim 11 wherein the repeatable exchange sort to which the working sequence is subjected is a quicksort that selects a central position in the working sequence as the pivot location.
19. The computer-readable storage device of claim 11 , the method further comprising:
identifying those items that should be included on the mth page of n items; and
sorting the identified items that should be included on the mth page of n items.
20. The computer-readable storage device of claim 19 , wherein sorting the identified items that should be included on the mth page of n items comprises using an insertion sort to sort the identified items that should be included on the mth page of n items.