Linear Classification has achieved complexity linear to the data size. However, in many applications, data contain large amount of samples that does not help improve the quality of model, but still cost much I/O and memory to process. In this paper, we show how a Block Coordinate Descent method based on Nearest-Neighbor Index can significantly reduce such cost when learning a dual-sparse model. In particular, we employ truncated loss function to induce a series of convex programs with superior dual sparsity, and solve each dual using Indexed Block Coordinate Descent, which makes use of Approximate Nearest Neighbor (ANN) search to select active dual variables without I/O cost on irrelevant samples. We prove that, despite the bias and weak guarantee from ANN query, the proposed algorithm has global convergence to the solution defined on entire dataset, with sublinear complexity each iteration. Experiments in both sufficient and limited memory conditions show that the proposed approach learns many times faster than other state-of-the-art solvers without sacrificing accuracy.

RDF and OWL are used as the data model and schema, respectively, to build the distributed knowledge base of the Semantic Web. The components in RDF models, subjects, predicates, and objects, are identified universally on the web, which makes it suitable for distributed operations. In this paper, we employ the distributed hash table (DHT) technology on peer-to-peer network to develop distributed RDF store. To take into account of ontology in RDF, we extend the chord ring to be two-level ring, where the first level is based on the ontology schema and the next one is on the RDF itself. The extension retains the complexity of O(log N) in maintaining and lookup message in an N-node system. The simulation results show that adding an additional level reduces the path length of message lookup. We design three-layered system architecture for the ontology-based distributed RDF store. We are developing a prototype according to the design in this paper to show how the two-level ring works.