CMSC 725 Fall 2013 project descriptions. If more information is needed, please ask Dr. Samet. Note that some of these project ideas are not enough by themselves and thus would logically be combined with related projects. All projects are individual projects. There are NO group projects. The goal of each project is to be able to get a research paper out of it. This is not a requirement but has happened a number of times. NEWSSTAND-RELATED PROJECTS: We have developed a number of systems for spatio textual search. 1. STEWARD: http://steward.umiacs.umd.edu/ 2. NewsStand: http://newsstand.umiacs.umd.edu/news/light 3. TwitterStand: http://twitterstand.umiacs.umd.edu/news The key idea behind all of these systems is the identification of words that correspond to geographic locations (e.g., does "Jordan" refer to the name of a person like "Michael Jordan" or does it refer to the country or river). If it refers to a geographic location, then we need to identify the appropriate instance (e.g., is "London" in England, Canada, etc.?). This work involves some linguistics and is generally known as "geotagging". Once the words have been correctly identified, we plot our results on a map. In other words, we associate documents with the locations that are contained with them. In other words, we can retrieve documents by location. More importantly, the query location is usually specified graphically by pointing at it using a map query interface. The advantage of using such an interface is that we need not know the exact name of the location. We just need to point at a nearby location. In other words, we are able to make use of synonyms in our queries, where the synonyms are restricted to being "spatial" (i.e., names of geographic locations). This is an example of "approximate search". STEWARD works with a collection of documents and attempts to identify all instances of geographic locations in each document and enables viewing a document with a map as well as finding all documents that contain a particular keyword. In addition, an attempt is made to determine a geographic focus for a document which is the most important location in the document from the point of view of being the subject of the document. Currently, the system works for a collection of documents from the following sources: A. HUDUSER: A collection of documents. B. PubMed: Abstracts of published biomedical articles. C. ProMED-mail: Mailing list postings about infectious disease outbreaks. D. News: Collection of news (old) NewsStand works with a set of 10,000+ HTML RSS news feeds. It cleans up the HTML so that the articles, images, and videos can be extracted. It then uses the TF-IDF representation of the articles to cluster them using an online clustering algorithm. A number of factors go into the clustering. In addition, the topics of the articles are determined (one of a small set). Images and videos are extracted and collected for each cluster and the articles are geotagged. The main version of NewsStand is web-based. However, a separate implementation of NewsStand also exists on a smartphone like the iPhone and the Android. TwitterStand works with Tweets. The key idea is to capture tweets that correspond to late breaking news. The result is analogous to a distributed news wire service. The difference is that the identities of the contributors/reporters are not known in advance and there may be many of them. The tweets are not sent according to a schedule. The tweets occur as news is happening and are noisy while usually arriving at a high throughput rate. Some of the issues include removing the noise, determining tweet clusters of interest bearing in mind that the methods must be online (i.e., clusters whose elements are constantly changing over time thereby reflecting the news cycle which is one of increasing volume as the topic becomes known, followed by a more steady decline as interest naturally fades), and determining the relevant location associated with the contents of the tweets, rather than the locations from where the tweets are sent. This is quite challenging and makes heavy use of the techniques developed for the NewsStand system. Possible Projects: 1. Introduce news summaries into NewsStand. This is similar to a system by a 17 year old kid that was recently sold to Yahoo. In some sense the pyramid style of news writing is such that one can cut off the article at any point and have a summary. A question is the quality of the summaries provided by the commercial system over just using the result of the pyramid style. 2. Incorporate a broader search capability into NewsStand. Currently, the search command only deals with words that appear in the headline. In other words, only they are indexed. The problem is that indexing all terms will require much work and storage. This is what Google does. Devise some form of lazy evaluation for indexing so perhaps that indexes are only built for articles that have been fetched by queries. This could be broadened to index all articles that appear in a cluster one of whose element articles has been fetched by a query. 3. Adapt STEWARD to deal with the Wikipedia. In this case, the result is a tool for looking at Wikipedia articles and providing a way to access the Wikipedia by location. Note that you will be identifying the locations using techniques similar to what is currently being used in STEWARD and NewsStand. Note that you are not using the "geotags" often provided in conjunction with the Wikipedia articles. However, you could do an evaluation of your own geotagging with that of the preassigned geotags. This is not simple in the sense that you need to be sure that you are doing something that does not already exist. Thus you will need to expend some tome investigating what is currently available. 4. Adapt STEWARD to deal with documents of the World Bank. For this you need to have a contact at this organization. There may be a chance of doing this due to contacts with Ihab Ilyas. This is a long shot project. 5. Adapt STEWARD to deal with documents of a government agency. For this you need to have a contact at the agency. 6. Adapt STEWARD to deal with a set of documents on disease spread monitoring. This is already in existence but could be beefed up. Rangjan Lan did such a project with ProMed mail in 2011 and ended up with a paper at the HEALTHGIS'12 workshop. See http://www.cs.umd.edu/~hjs/pubs/healthgis12.pdf In particular, something like this could be done by reaching out to Rita Colwell. Again, this is a long shot project which will require some initiative. 7. Adapt STEWARD or NewsStand to monitor mentions of brands in the news. In the case of NewsStand this could be done by adding a "Brand" layer much in the same spirit as currently done for the disease and people layers. One possible source for names of brands is the website brandtags.com which lists not only brands but the most common words associated with them. After poking around a little online, one of the most comprehensive lists is found at http://www.kelkoo.co.uk/bd-brands. Its hard to find an authoritative source. Since brands are somewhat fluid and being created and destroyed all the time, it would be tough to maintain a current up-to-date list. This project came at the suggestion of Prof. William Rand of the Smith School of Business. 8. Develop methods to determine the "geographic focus" of a document, individual news articles, and also clusters of news articles and compare them. In particular, you will need to conduct an evaluation. The efficacy of your method may differ depending on the underlying input. 9. NewsStand currently uses a single server. The architecture of NewsStand is described in the following paper http://www.cs.umd.edu/~hjs/pubs/newsstand-arch.pdf a broader description is given in: B. E. Teitler, M. D. Lieberman, D. Panozzo, J. Sankaranarayanan, H. Samet, and J. Sperling. NewsStand: A new view on news. In GIS'08: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 144-153, Irvine, CA, November 2008. http://www.cs.umd.edu/~hjs/pubs/newsstand-acmgis2008.pdf Investigate quality of service issues for NewsStand. In other words, investigate how many users the current implementation of NewsStand can support and the query mix that would yield a meaningful performance study. Determine if the quality of the service can be improved by making use of a cloud-like architecture such as available on Amazon and develop a prototype. 10. Investigate what aspects of the NewsStand pipe system could be sped up via use of GPUs. For example, look at the document ingestion system (i.e., cleanup module) as described in a paper that we wrote found at /nfshomes/codepoet/work/papers/cleaner/main.pdf Alternatively can we use several servers on the cloud to perform this task. The idea is to speed up the document ingestion component possibly by distributing it so a number of servers are cleaning up the documents in parallel or possibly using a GPU to do the task. 11. Investigate whether latency (distance from UMD) has an effect on the performance of NewsStand (both app and web versions). Investigate the use of a mirror site. Also Investigate how quickly data received by the NewsStand clients can be rendered in NewsStand's interface. The speed of rendering greatly affects NewsStand's perceived interactivity. Determine if the rendering time can be shortened somehow. 12. Investigate the use of GPUs for clustering the news articles. Some work has been done on this already by Ben Teitler. The goal is to obtain speedups over a sequential approach. The speedup should be more than a factor of 2, which is what was obtained by Ben Teitler. DONE! 13. Investigate a distributed clustering algorithm for NewsStand. The idea is to distribute the computation of the similarity function (cosine) with every feature vector and figuring out which ones can be pruned. This is an alternative solution to the one using GPUs in 12, although it may also make use of GPUs. Note that GPUs have a SIMD (single instruction, multiple data) architecture, with many cores all executing the same program, but with different data input. All the processors are able to access a single large shared memory space, which is relatively slow, as well as smaller cache memories on individual processors, which are faster. GPUs are optimized for arithmetic-heavy tasks which are frequently encountered in graphics processing, which makes them suitable for heavy number crunching. On the other hand, distributed architectures (e.g. MapReduce) involve many separate computers, each with dedicated and possibly non-uniform hardware, which communicate over a network. Both the GPU and the distributed architectures are readily programmable using general purpose programming languages. 14. Suppose that each user of NewsStand has access to a device with computing power as is planned for the soon to be released NVIDIA tablet which has a local GPU. Can you download some of the functionality of NewsStand on these local clients. For example, different RSS news feeds can be ingested by these local clients. Devise a scheme where, in essence, NewsStand is being outsourced. 15. NewsStand's geotagging module makes a number of errors. In particular, we have observed repeated errors for certain locations. Your job is to run NewsStand extensively and identify entities that are wrongfully identified as locations (e.g., "George" in South Africa and other first names that are often wrongfully interpreted as geographic locations) or are associated with the wrong geographic location (e.g., "Georgetown" being placed in Guyana instead of being associated with "Georgetown University" in Washington D.C.). Some example locations are provided below. This is not exhaustive but gives you some idea of the scope of the problem. Georgetown Northern District Batman Man Barcelona Santa Cruz Valencia Alexandria Athens Columbus Columbia Paris London Berlin Moscow Salem Springfield Dover Newark Augusta Portland St. Louis Dublin Hollywood George One possible approach is to have a specialist for the various locations. For example, in the case of "Georgetown" the idea is to be able to recognize all possible usages of it when it is the name of the University in Washington, DC. In this case, the references are often to the athletic teams. It would be interesting to see the extent to which the general geotagging module in NewsStand can be improved, if at all, using these specialized packages. Several students can be assigned this project with a competition at the end to see who does best. SHANG FU PENG has looked at this problem but no definitive solution. 16. Investigate the utility of time-dependent geotagging where the resolution of a possible toponym depends on its current usage. For example, "George" may appear a lot in the news at a certain time and thus an interpretation as a location may be less probable. 17. NewsStand has a topic detection module, which identifies the general topic of an article (e.g., business, sports). Evaluate its quality and compare with other work in the literature. Try to develop a better method. SAMET AYHAN tried this topic in 2011 but inconclusive results. 18. NewsStand currently only works for articles in English. This means that only news sources in English are handled. The scope of NewsStand could be significantly increased by including articles in languages other than English. The problem here is that these articles would not be properly clustered as the TF-IDF mechanism is language sensitive. Also, geographic names differ in the various languages. One suggestion is to use English as the canonical language and use Google Translate to convert the foreign language articles to English prior to clustering them. This would be done only internally while the output of NewsStand would still refer t pairs (i.e., hash table), such that given any pair of source and destination vertices, and an estimation error bond \epsilon, the use of an approximate distance oracle of size O(n \epsilon^2) enables on to obtain the \epsilon-approximate nearest neighbor distance by making O(log n) accesses to the hash table. The term n is the number of vertices in a road network. There are couple of research problems to solve here: a) Distance oracles are expensive to compute since you need the distances between every pair of vertices in the road network. However, there are many obvious ways of cutting corner here to achieve real speedups. Can you figure out a way of scaling these oracles to work on a data set spanning the whole of USA? b) Can you then map the distance oracles to a key-value store to enable the use of cloud computing infrastructures such as MapReduce for performing operations on large road network datasets? Also, can you reduce the number of access to be one or two rather than O(log n). This is an easy part since the mechanics of it are quite easy. The outcome of this project could be a really useful service on the web where thousands of people can pose distance queries and can get approximate network distances in fractions of seconds. 5. Incremental nearest neighbor algorithm: A. for Frechet distance See SIGSPATIAL'12 paper titled A GPU approach to sub-trajectory clustering using the Frechet distance Joachim Gudmundsson, Nacho Valladares B. Incremental nearest neighbor algorithm for Earthmover distance See papers by David Jacobs and Leo Guibas 6. Look into Charikar and Broder's work on LSH (Kanellakis award) and figure out what how it is related to the example in Samet's "Foundations of Multidimensional and Metric Data Structures" as well as try to incorporate it into the text. Charikar's paper on simhash: M. Charikar. Similarity estimation techniques from rounding algorithms. Proceedings of STOC. pp. 380-388. 2002. http://www.bradblock.com.s3-website-us-west-1.amazonaws.com/Similarity_Estimation_Te+chniques_from_Rounding_Algorithms.pdf It could be that the example in Section 4.7.4 on pages 711-716 in Samet's Foundations of Multidimensional and Metric Data Structures that uses binary digits is in fact simhash. For a good treatment of simhash, see http://matpalm.com/resemblance/simhash/ Broder's paper on minhash: A. Z. Broder. On the resemblance and containment of documents. Proceedings of IEEE Conference on Compression and Complexity of Sequences. pp. 21-29. 1997. http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf 7. Provide simple pseudo code Yi and Samet ICDE'13 paper in the style of Samet's algorithms and see if it can be extended to metric spaces. 8. Look into structured graphs work of Leila De Floriani and see if it can be applied to social networks. Need to look up her papers. 9. Spatially-oriented social network identification. In other words, investigate how to incorporate knowledge of spatial proximity (also temporal proximity). 10. Is it possible to use differential privacy in a spatial context? SHANGFU PENG is an expert here. 11. Finding reliable tweeters of news. Nick Gramsky started this work as a class project but the definitions of "good" tweeters are quite weak. Also, the experimental results are inadequate. Needs much more work but is a hot topic. See the report at: http://www.cs.umd.edu/~hjs/seederfinder.pdf 12. Parallel graph traversal in a distributed computing environment. The problem of graph traversal is concerned with searching through graph nodes to find solutions with respect to a certain optimization criteria. For example, the problem of finding the k nearest supermarkets with respect to a location q in a road network can be modeled as a problem of traversing the road network to find a supermarket p (in a set of supermarkets) which minimizes the network distance D(q,p). This project is concerned with applying the distributed computing frameworks, e.g, MapReduce, Distributed GraphLab, to formulate different graph traversal algorithms for different spatial-network query problems, e.g., range, nearest neighbor, reverse nearest neighbor, skyline and distance join queries. 13. BlogStand: an analogous system to NewsStand but for Blogs. In other words we want to geotag blogs and provide a map query interface to them. This involves identifying blogs, etc. The work is analogous to NewsStand but probably less images and videos. 14. Survey of spatio-textual join papers and work. a. ICDE 2013 b. IEEE TKDE "A Prefix-Filter based Method for Spatio-Textual Similarity Join" by Liu, S. ; Tsinghua University, Beijing ; Li, G. ; Feng, J. To appear. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6517849 Try to embed such a query into NewsStand 15. Connected component labeling on GPU and maybe other operations. E.g., http://scholar.google.com/scholar_url?hl=en&q=http://link.springer.com/article/10.1007/s11265-013-0780-0&sa=X&scisig=AAGBfm2l2qu-nTRZNaFxYCtXYksN8KX-dg&oi=scholaralrt 16. Can you adapt the following methods to spatial data like quadtrees or some other appropriate variant: Optimizing bitmap indices with efficient compression K Wu, EJ Otoo, A Shoshani. ACM Transactions on Database Systems (TODS) 31 (1), 1-38. Look at other work by K. (John) Wu especially On the performance of bitmap indices for high cardinality attributes. K Wu, E Otoo, A Shoshani. Proceedings of the Thirtieth international conference on Very large data 2004, 24-35. 17. Look into what is being done with news by Jure Leskovec at Stanford. Seems to have 4 billion news articles. http://engineering.stanford.edu/news/big-questions-big-data-stanfords-jure-leskovec 18. Ambuj Singh suggestions of more complicated queries in NewsStand like "is there an article about X in an Israeli paper" and "no article about Y in an Irish paper"? etc. In other words, we are looking for queries involving the various options in NewsStand and how to express them within the touch framework. Need to get more queries. 19. Implement database of NewsStand using Vertica community edition and see if it is possible and how it performs vis-a-vis PostgreSQL. Need to consult with Marco Adelfio. 20. Reimplement the SAND Internet Browser using the Vertica community edition. This means substituting the SAND homegrown database by the Vertica database. Is this possible? Need to ask Jagan and also if it is worth it in the sense of what we would gain from doing so. This would mean that the various algorithms for computing the incremental nearest neighbor and range queries would need reimplementing. This also means investigating how to use a pointerless quadtree in this environment or if one would use a pointer-based quadtree. One option is to store quadtrees in an array representation where pointers are array indexes. Problem is that there is little ability for random access and need to start at the root. Also, does not support updates 21. Ask Vertica for some of the queries that their spatial customers would like to execute and see if we can develop algorithms. Were worried about representing polygons with holes. How to do with PMR and PM2 quadtrees. 22. Does it make sense to use MongoDB for spatial data such as the SAND Internet Browser? 23. Does it make sense to use MongoDB for NewsStand instead of PostgreSQL? Need a performance study. 24. K. Wu results on connected component labeling: Kesheng Wu, Ekow Otoo, and Kenji Suzuki Optimizing two-pass connected-component labeling algorithms Pattern Analysis and Applications. June 2009, Volume 12, Issue 2, pp 117-135 Claim to be fastest method of doing connected component labeling. Compared it with the following algorithm: as being of the same type as the Dillencourt/Samet/Tamminen algorithm. However, its not clear that Florio and Gustedt implemented the Dillencourt/Samet/Tamminen algorithm. So, a comparison with the Wu/Otoo/Suzuki may be worthwhile. Fiorio C, Gustedt J. Two linear time union-find strategies for image processing. Theor Comput Sci 154(2):165181. 1997. 25. Look at the maps in http://www.washingtonpost.com/blogs/blogpost/post/40-maps-that-explain-the-world/2013/08/12/5775d214-0364-11e3-bfc5-406b928603b2_blog.html and show how the information that they capture could be presented using queries in the SAND Internet Browser. This means expressing the underlying data as spatial relations and then formulated queries using the primitives available in the SAND Internet Browser possibly using the functionality of SAND-Tcl. See http://www.cs.umd.edu/~hjs/pubs/sandtcl.ref.pdf 26. Fix Mapping Apps of Apple Maps, Google Android Maps, and iOS Google Maps to show entire world at full zoom out level. In other words, enhance API and App to show whole world as in iOS5. Otherwise, one cannot get the notion of browsing a newspaper to really work as too slow and cannot get the big picture. SPREADSHEET-RELATED PROJECTS: Make use of the availability of large quantities of geospatial spreadsheets (i.e., spreadsheets containing geographic references). There are many such spreadsheets on the Web and together they can be thought of as a very large distributed database. HTML tables, PDF tables and others can also be considered as spreadsheets for these purposes. But there are two problems with making use of this database of spreadsheets: 1) spreadsheets are messy and 2) it's not obvious how data can be related between spreadsheets. 1. Improve geotagging accuracy of spreadsheets and data tables. The GeoWhiz project introduces a framework for geotagging lists, but could be improved by consulting proximity features, other measures of prominence, or additional place type ontologies. 2. Allow spatial query operations to be performed on the large collection of geospatial spreadsheets. Similar to the SAND browser, it could be useful to search or browse the database of geospatial spreadsheets using common spatial operations. Examples: - Find spreadsheets with a "similar" distribution of points to a query point set. - Find spreadsheets with a "similar" distribution of points to a query spreadsheet. - Find spreadsheets with the highest concentration of points within a query window. - Find spreadsheets with points only within a query window. NOT WELL-DEFINED PROJECTS: 1. Volunteer geographic information systems a. Workshop at SIGSPATIAL'12 b. http://scholar.google.com/scholar_url?hl=en&q=http://onlinelibrary.wiley.com/doi/10.1111/tgis.12039/full&sa=X&scisig=AAGBfm05uni8BuefGPiF3h4MpWZAMeZaOQ&oi=scholaralrt 2. Sentence Similarity with spatial data. E.g., http://scholar.google.com/scholar_url?hl=en&q=http://www.aclweb.org/anthology/N/N13/N13-1089.pdf&sa=X&scisig=AAGBfm0jdx1nhl4y7qi1i3SMaZ0Wf5xLRQ&oi=scholaralrt 3. C. Garth, K. Joy. Fast, Memory-Efficient Cell Location in Unstructured Grids for Visualization. IEEE TVCG 16(6), 1541-1550, 2010. Mentioned in http://www.iwr.uni-heidelberg.de/groups/CoVis/Teaching/VNT_SS13/vis2-4_effDatenstrukturen.pdf 4. A. Telea. Data Visualization. AK Peters Ltd., 2007. Mentioned in http://www.iwr.uni-heidelberg.de/groups/CoVis/Teaching/VNT_SS13/vis2-4_effDatenstrukturen.pdf 5. See VTK Visualization Tooklit (Kitware) 6. Text summarization via Hidden Markov Models (Dianne O'Leary SIGIR 2001) http://dl.acm.org/citation.cfm?id=384042 Mike Szaszy is a candidate for working on this topic 7. Measure clustering quality Mike SZASZY project 8. Look into paper on toponym resolution and see what they do. Text-Driven Toponym Resolution using Indirect Supervision M. Speriosu and J. Baldridge Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1466-1476, Sofia, Bulgaria, August 4-9 2013. http://scholar.google.com/scholar_url?hl=en&q=http://acl.eldoc.ub.rug.nl/mirror/P/P13/P13-1144.pdf&sa=X&scisig=AAGBfm1kAADgLLcMnUTnjIfQEU_hnq0aEw&oi=scholaralrt This paper encourages using the presence of clues like "lobster" to help resolve "Portland" in favor of "Maine" over "Oregon". This comes out of linguistics literature. Examine it. This is also related to use of concepts by Gianluca. 9. Fiona from Australia sent following reference: Kjetil e Vaage (2012) Sensing the News: User Experiences when Reading Locative News. Future Internet 2012, 4, 161-178; doi:10.3390/fi4010161 10. Look into the European LEILAS "EruoStars" project at http://www.leilas.eu/ This website has information about work plans for the project. Try to find out what they actually accomplished. This means finding technical reports, etc. At the moment, all that the site contains are descriptions of tasks for a proposal. It was started in 2011. So, there should be some results. One four page paper in French, which is lacking in details, can be found at http://scholar.google.com/scholar_url?hl=en&q=http://www.viseo.net/sites/default/files/viseo-group/article-leilas_representation_geospatiale_d_ensemble_de_documents_textuels-ecg2013.pdf&sa=X&scisig=AAGBfm3KqeEfEYf5cqS94Xnq53QuYLOHYw&oi=scholaralrt 11. The GeoXLS (ACMGIS'11) system is a search engine that allows users to submit a set of locations as a query object Q and to find documents containing locations similar to those in Q. Search results come from a collection of geotagged web documents, specifically a vast collection of spreadsheets obtained from the Web. The results are ranked according to their similarity to Q, where similarity is measured using the Hausdorff distance or modified Hausdorff distance (a variant that reduces the effect of outliers). For example, given a point set query consisting of locations where a disease outbreak has been reported, one could search a database of previous outbreaks to find others with similar geographic distribution. The search algorithm iteratively computes estimates of the distances between the query point set and the collection being searched, to prune the search space without computing the Hausdorff distance from the query set to every other point set in the collection. a. The system currently searches point sets from a collection of spreadsheets downloaded from the Web. Identify other possible collections of point sets to search, and extend GeoXLS to search these point sets. One possible source of point sets is the Wikipedia. b. Construct a GPU implementation of the incremental Hausdorff search algorithm utilized by GeoXLS. c. The Hausdorff distance and modified Hausdorff distance are both computed by identifying the nearest neighbor of each point, but a single point can be used as the nearest neighbor of many points in the other point sets (for example, a point set with 100 points in College Park and 1 point in London will be "similar" to a point set with 1 point in College Park and 100 points in London by these measures). Identify a distribution-sensitive similarity measure between a pair of point sets that limits this effect, and extend GeoXLS to support it. 12. Apply methods such as Hausdorff distance computation to the problem of Hurricane detection and tracking similar ones. This is quite vague. It requires a person who is a domain expert in this area. 13. Compare NewsStand with Pulse and Flipboard and other online news aggregation sites. What enhancements could NewsStand use? 14. Spatial keyword queries - see SIGMOD'13 paper and references cited therein Given a location and set of key words a. Find all or minimum set of objects that covers a set of keywords. b. Could minimize area of covering region in a 15. Spatial join papers of Alimaki group at EPFL - SIGMOD'13, EDBT, SSDBM'13, etc. 16. SIGMOD'13 paper in Session 21 on Tweets and finding all garage sales withing 24 miles of a specific location. The idea is to constantly update the query results as events come up rather than static. Currently, updates only happen in TwitterStand/NewsStand when the map moves a bit. 17. SIGMOD'13 paper on spatial keyword searches where want objects with certain properties from a minimal spatial area, etc. Not very novel but could do some extensions. 18. Look into road network paper at SIGMOD'13 that improves on Samet SIGMOD'08 paper. 19. Raymond Wong paper at SIGMOD'13 about bottleneck problem and compare with Efrat and Itai paper 20. Investigate notion of implementing a point quadtree variant with a splay strategy. In other words, how do you splay the data points? It seems similar to the notion used by Samet in See H. Samet. Deletion in two-dimensional quad trees. Communications of the ACM, 23(12):703--710, December 1980. to delete where we make the closest node to the deleted node the root of the new point quadtree. The splay tree of Tarjan and Sleator does this by rotation operations while we do it with one operation. However, the result is the same in the sense that the replacement node becomes the new root node. The only difference is that we actually rebuild the underlying point quadtree with the new root, while in the one dimensional splay tree, we move the deleted (or accessed) node to the root via rotation operations which preserve the structure of the binary search tree. The whole idea is analogous to a self-organized file. This was motivated by listening to Eunhui Park's Ph.D. defense although she was unaware of this relationship. QUESTION: Can Samet's point quadtree deletion algorithm be expressed in terms of splay operations? QUESTION: Samet observed that, empirically, the total path length decreased as a result of the deletion operation. Also a logarithmic execution time was observed. a. Can you prove the logarithmic deletion time? b. What about an amortized logarithmic deletion time? c. Can you prove that the total path length decreases in 2d? What about in 1d? 21. Eunhui Park Thesis defense observations: a. Look into the scapegoat tree which is similar to the splay tree but involves no rotations (p. 13). b. The treap is analogous to the priority search tree except that it uses a binary search tree on the values and a heap on priorities (assigned to the values at random so that we don't have the non-randomness of the values which means that sorted data might not be a random property). In essence, the structure is nothing more than a Cartesian tree. The concept is analogous to the skip list except that no lists are used. c. The splay quadtree is a misnomer. It is really a splay BBD-tree but it does not sound so exciting. There cannot be a structure such as a splay quadtree (really a PR quadtree), because the structure's shape is independent of the order of insertion. The BBD-tree can be splayed because the aggregation process is decoupled from the partition process. d. Pointless to talk of having a splay red-black tree as this is nothing but a 2-3 2-3-4 tree (order 3 or order 4 B-tree). The fact that these corresponding B-trees are balanced makes it pointless to ask about how to splay them as all this can achieve is rotation and is much more complex to specify in the framework of a red-black tree than in the framework of a B-tree. e. It would be nice to have an example of a skip quadtree (p. 19) using the point data from Samet's data. f. Explain Chan's method using Samet's data (p. 22). g. Check Fair Split Tree of Kosaraju and Callahan (pp. 23-24) and see if it can be shown using Samet's data. h. Give an example of spanners (p. 24) using Samet's data. i. Explain concept of doubling dimension (pp. 25-26). j. Ask Jagan about homogeneous well-separation (p. 80). k. Ask Jagan about the well-separated pair construction algorithms in the thesis. l. What is the relation of net trees and r-nets to traditional metric space data structures like mb-trees, etc.? ---------------- NSF Key Value Store Proposal Tasks ---------------- RESEARCH TIMELINE: Year 1: A. Point Cloud 1. Derive a data partitioning scheme for a large point cloud. 2. Formulate a set of parallel algorithms for querying large point clouds. 3. Evaluate the efficiency of the proposed parallel algorithms by analyzing factors like the degree of parallelism, communication cost and granularity. B. Loose Quadtree 1. Implement a distributed variant of the loose quadtree for indexing moving objects. 2. Derive parallel query algorithms for the distributed loose quadtree. 3. Evaluate the effectiveness of the distributed loose quadtree by comparing it to grid-based moving object indexes. C. Multiresolution Range Query 1. Formulate a distance-preserving hashing technique which enable range queries to be evaluated via simple lookup operations. 2. Compare and contrast the performance of the proposed technique to a classical solution based on hierarchical indexes. 3. Evaluate the effectiveness of the proposed hashing technique by applying it to real-world online map applications. Year 2: Distance Oracle 1. Investigate the possibility of mapping distance oracles to a key-value store. 2. Devise a method to provide access to the key-value store representation of the distance oracle using one or two accesses, most of the time. 3. Demonstrate the applicability of our methods to Internet-scale applications by studying the throughput, average access times, and the quality of the answers. 4. Deploy the distance oracle in complicated query processing scenarios, especially those in location-based services and local searches. 5. Devise a set of publicly available distance oracles for the entire United States for different values of $\epsilon$. Year 3: Distributed Graph Traversal 1. Derive a parallel graph traversal method method for a message-passing-based distributed computing framework like Pregel. 2. Derive a parallel graph traversal method which does not require communication between tasks for the MapReduce framework. 3. Formulate parallel algorithms for different query problems (e.g., range, nearest neighbor, reverse nearest neighbor, and distance join queries) using the derived methods. 4. Compare and contrast the performance of the messaging-passing-based algorithms with algorithms that do not require communication between parallel tasks in different processing environments. The main impact of this project is expected to be a spatial database management system which supports a wide range of spatial query types and is capable of "scaling out" to handle a large amount of spatial data. This will enable spatial applications such as online mapping, computer aided design, online gaming and scientific simulations to store terabytes of spatial data and to execute queries such as shortest path and self-join on them. Thus the improvement will lie in the scale and range of the sizes of the data sets that we will be able to handle. ----------------- NSF GeoMultiMedia Proposal Tasks ----------------- RESEARCH TIMELINE: Year 1: Geotagging and Clustering Improvements for News and Tweets a. Identify features to be used in a machine learning based approach b. Evaluate results of using machine learning vis-a-vis current rule-based approach c. Compare results with existing systems such as OpenCalais and Placemaker d. Develop methods to identify reliable seeders for TwitterStand e. Develop GPU-based document clustering based on an analogy to sparse matrix multiplication The evaluation of the effectiveness of these components will be ongoing. In the first year, we will construct ground truths which consist of news articles that we deem to contain representative articles with the type of geographic locations that we wish to recognize and resolve correctly. In addition, we will make use of the error feedback mechanism to collect geographic locations that the system has consistently failed to recognize or has resolved incorrectly. These articles will form a set which will be tested from time to time to see if subsequent system improvements result in the errors disappearing. Year 2: Image Similarity Using the Associated Text a. Devise system to retrieve newsworthy images and videos using a map query interface b. Develop techniques for context-based image similarity search c. Identify image transformation types that result in partial-duplicate images d. Apply partial-duplicate image detection as filtering mechanism for image queries. The evaluation will be conducted using a ground truth which is a set of images that we have been collecting during the first and second year that are representative of the type of similarity which we would like the system to be able to detect. The evaluation will be ongoing with feedback for enhancement. Year 3: Use of Language Translation Service for News Text a. Evaluate translation services (e.g., Google Translate) in terms of preservation of the cluster property b. Evaluate effectiveness of using translation of cluster centroids as cluster representatives for foreign language documents c. Evaluate use of non-native language documents to find similar clusters in the native language d. Use Arabic language news web sites to evaluate translation quality e. Identify reliable seeders for TwitterStand in other languages such as Arabic. The evaluation in this context is more of a qualitative nature in the sense that what we are doing is trying to incorporate the results of the translation service and determining if it makes sense to do so and if so, in which components of our system. The focus on Arabic in the case of seeders for TwitterStand is primarily because we have access to a collaborator who has done much work in processing news sites in the Arabic language. We hope to draw on his insight in processing Arabic tweets. The identification of seeders will be ongoing with the final evaluation done in the third year. Identification will use factors such as being the first to tweet on an important news topic, the number of tweets by others on the same topic, the number of different topics tweeted on, and the extent to which the seeder re-tweets (a negative factor). Of course, we also need to define the newsworthiness of the topic. This is done by making use of the url that the tweet usually points at and whether there are existing news articles in its cluster. The evaluation is done over an extended time period. POSTDOC The postdoc will be working on the geotagging module which is a key to the success of the system. The postdoc will focus on the machine learning component in the first two years while also investigating the feasibility of the development of a language-independent geotagger. This will most likely be based on machine learning as the rule-based techniques have a large language-dependent component. The postdoc will also work on investigating the extent to which the translation preserve clustering.