Fast Algorithms Using Minimal Data Structures for Common Topological Relationships in Large, Irregularly-spaced Topographic Data Sets

Digital terrain models (DTM) typically contain large numbers of postings, from hundreds of thousands to billions. Many algorithms that run on DTMs require topological knowledge of the postings, such as finding nearest neighbors, finding the posting closest to a chosen location, etc. If the postings are arranged irregu- larly, topological information is costly to compute and to store. This paper offers a practical approach to organizing and searching irregularly-space data sets by presenting a collection of efficient algorithms (O(N),O(lgN)) that compute important topological relationships with only a simple supporting data structure. These relationships include finding the postings within a window, locating the posting nearest a point of interest, finding the neighborhood of postings nearest a point of interest, and ordering the neighborhood counter-clockwise. These algorithms depend only on two sorted arrays of two-element tuples, holding a planimetric coordinate and an integer identification number indicating which posting the coordinate belongs to. There is one array for each planimetric coordinate (eastings and northings). These two arrays cost minimal overhead to create and store but permit the data to remain arranged irregularly.

The Black-White Achievement Gap Amongst Struggling Readers: A Case Study of Early Intervention Outcomes in Massachusetts

A number of analyses of large data sets have suggested that the reading achievement gap between African American and White U.S. is negligible or small at school entry, but widens substantially during the school years because African American students show slower rates of growth in elementary and secondary school. Identifying when and why gaps occur, therefore, is a an important research endeavor. In addition, being able to predict which African American children are most likely to fall behind can contribute to efforts to close the achievement gap. This paper analyzes first grade and third grade data on African American and White children in Massachusetts who all were identified in first grade as struggling readers and enrolled in Reading Recovery—an individualized intervention. All the children were low-income and attending urban schools. Using Observation Survey data from first grade, and MCAS Reading data from 3rd grade, we found that the African American and White students made equal average progress while in first grade, but by the end of third grade showed a large gap in MCAS proficiency rates. We discuss the results in terms of school quality, reading development, dialect issues, testing formats, and the need to provide long-term support to vulnerable learners.