Hierarchical Data

Finally we submitted a paper on Change Detection in Hierarchical Data. People usually talk about change in data or data streams without considering hierarchy -- for example, one is usually happy with knowing what is the percentage increase/decrease in sales volume in Walmart in California. We address the problem of detecting changes in data where attributes are hierarchical. For example, a manager in Walmart might have information about sales which is organized by hierarchy -- state/county/city/zip code in US. One can pose a question -- if the sales volume under all the zip codes in San Fransisco have doubled, what is the parsimonious way to represent the change ? We say, sales volume in SF has doubled. Our approach captures such changes with maximal generalizations and thus captures trends and counter-trends. We reduce the problem to a weight assignment problem over hierarchical tree structure under some constraints and propose efficient linear-time optimal algorithms.