SortTables - CIKM '95

Overview

• Browsing
• SortTables: A System for Browsing
• Design Goals and Implementation Experience
• Data Structures
• Future Directions

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

Present a subset of items for which

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

Data Structures

Data Structures: The Bounds Tree

Data Structures: The 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

Copyright 1994-2009, William C. Wake - William.Wake@acm.org