XML 스트림을 통한 검색 알고리즘

Question

스트리밍 XML 문서를 통한 광범위한 검색을위한 알고리즘/기법에 대한 제안을 찾고 있습니다.

<foo> 
    <bar name="aaa" > 
     <grah name="aab" /> 
     .. 
    </bar> 
    <bar name="bbb" /> 
    <bar name="ccc" /> 
    <bar name="ddd" /> 
    <bar name="eee" /> 
... up to 10,000 entries 
</foo> 

1 단계 요소의 수는 제멋대로입니다. xml의 ​​사용은 또한 제 통제에서 벗어났습니다. 나는 xml을 전처리 할 수 ​​있지만 XML을 색인화 할 수는 있지만 (forseeable future의 경우) 전체 XML 문서를 요청 단위로 메모리에로드 할 수 없다.

현재이 작업을 수행하기 위해 libxml의 스트림 읽기 기능을 사용하여 순차적으로 검색하고 있습니다. RAM/요청의 고정 된 양을 많거나 적게 소비하며 일반적으로 3k 행 미만의 모든 것에 대해 매우 반응적이며 가장 인기있는 결과 캐싱이 도움이되지만 거의 모든 최상위 요소가 특정 단계에서 공격을받습니다.

최근에 우리는 레벨 1 요소가 최대 10,000 개의 요소 크기 였고 끝까지 더 가까운 일치가 서버 응답과 관련하여 용납 될 수없는 많은 수의 큰 파일을 처리해야했습니다.

지금까지 Intoselect와 Quickselect는 검색 공간을 줄이고 합리적인 것으로 보았습니다. 내가 코드를 작성하기 전에 간과 한 다른 아이디어 나 알고리즘이 있는지 알고 싶습니다.

Answer 1

검색 요구 사항이 무엇인지 또는 검색 할 텍스트가 어떤 모양인지 자세히 설명하지 않습니다. XML 자체가 관심이 없다고 가정하고 libxml을 사용하여 수행하는 스트림 구문 분석을 통해 XML 데이터가 정제되고 더 쉽게 검색 할 수있는 객체를 지속적으로 만들 수 있다고 가정합니다.

물론 XML 문서를 eXist과 같은 XML 데이터베이스로 이동할 수 있습니다. 원래 XML을 유지하려는 경우 매우 유연하지만,이를 버리면 XML 문서의 본질을 저장하는 다른 방법을 찾습니다. 검색 할 데이터

XML을 사전 프로세스로 작성할 수 있으므로 XML도 자주 변경되지 않는다고 가정합니다. 이러한 가정이 맞으면 Lucene과 같이 검색 중심 데이터베이스에서 검색 할 텍스트를 인덱싱 할 수 있습니다. 당연히 검색 알고리즘을 직접 만들 수도 있지만, 쿼리 캐싱 및 기타 등등을 사용하여이를 수행하는 오픈 소스 솔루션이 있으므로 기존 솔루션 중 일부를 살펴 보는 것이 좋습니다.

검색 자체가 크게 다르지 않은 경우 XML의 데이터에서 JSON 개체를 만들고 답변이 거의 들어있는 사전 정의 된 인덱스를 사용하여 문서 데이터베이스 (예 : MongoDB 또는 CouchDB)에 저장할 수 있습니다. 메모리 내에서 수행하려는 검색에 적용됩니다.

귀하가 취해야 할 모든 해결책을 모르기 때문에 명확한 권장 사항을 제시하기가 다소 어려울 수 있지만, 몇 가지 아이디어가 있습니다.