SortTables – CIKM ’95

William C. Wake and Edward A. Fox

Nov. 30, 1995

Presentation at CIKM ’95

Overview

Browsing: Physical

Access to the item
Potential access to all the items
Sense of neighborhood
Zooming
Serendipity

Browsing: Online

Like physical browsing,
but without physical access
Speed
Remote browsing
Multiple arrangements
Flexible manipulation

Browsing: Examples

Smalltalk browser
NeXT directory browser
Netscape WWW browser
Envision result set display

SortTables: A System for Browsing

Table metaphor
Support for
- Movement
- Sorting
- Searching
- Restriction
Example (PostScript)

Design Goals

Simple metaphor with high interactivity
Range restriction and multiple orderings
View the whole database
Integrate browsing and searching
Progressive utility
Sense of progress

Implementation Experience

Spreadsheet prototype – test ideas
NeXT graphical interface –
explore interface implementation
VT100 versions
- Portable
- Formative evaluation
- Database implementation testbed

Implementation Evolution

Spreadsheet prototype (omitted)
NeXT GUI version. Used WAIS to locate items, then sorted them on the fly.
Original VT100 version.
VT100 version shown in paper. As revised from original formative evaluation.
Current VT100 version. Note that it now shows ranges of attribute values.

Experience: Formative Evaluation

Core interface acceptable
Add page keys
Remove undo, exclusion
Sorting as a bottleneck

Data Structures

“Sorted orthogonal range queries”
Present a subset of items for which

For all i: min[i] <= attr[i] <= max[i]

sorted by attr[j]

Data Structures

“Thread file” – like cards connected by string
Thread File – like cards connected by a string

Data Structures: The Bounds Tree

Top three layers of the bounds tree
Top three layers of the bounds tree

Data Structures: The Bounds Tree

The full bounds tree

Data Structures: Space Requirements

Data Set
     Envision   Library        Item
     --------   -------        ----
       100K        1M          Records (N)
         6         5           Columns (C)
        16        64           Records/Bucket (B)
        22M      167M          Record Space (disk)
         7M       47M          Thread File Space (disk)
         2M        4M          Memory required (RAM)

Data Structures: Space Requirements

Bytes    Location   Type
       -----    --------   ----
        4CN      disk      Buckets
        4CN      disk      Leaf layers of bounds tree
       CN/8      memory    Record bits ("known bad")
     CN/(8B)     memory    Bounds bits ("known bad")
  8(C^2)N/B      memory    Slice of bounds tree

Future Directions

Data structures
Graphical user interface
Other data sets
Evaluation